A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
The present invention relates to compilers and programming languages for computer systems. More particularly, the present invention relates to a method and apparatus for efficiently accessing variable-sized, dynamically allocated arrays.
Certain programming languages, such as the FORTRAN programming language, facilitate operations on variable-sized dynamically allocated arrays. In order to manipulate such arrays, these programming languages maintain certain information. This information includes static information, such as the type and rank of the array, which does not have to be tracked during run time. This information also includes dynamic information, such as the allocation status of the array, the locations of the array elements, and the array bounds in each dimension. These dynamic properties can change, and hence, must be tracked during program execution.
Most programming languages that support variable-sized dynamically allocated arrays, such as the FORTRAN programming language, maintain this information in a data structure known as an xe2x80x9carray descriptorxe2x80x9d (or informally, as a xe2x80x9cdope vectorxe2x80x9d).
Referring to FIG. 2, in an existing array descriptor data structure 200, the array descriptor data structure 200 comprises a fixed part 202 followed by a sequence of triplets, wherein the number of triplets equals the rank (number of dimensions) of the array. In the example illustrated in FIG. 2, the fixed part 202 includes a start address 204 (actual origin) of the array as well as a virtual origin address 206 of the array. The start address 204 points to the starting location of the array of data values 226. The virtual origin address 206 contains an address of a virtual array element, possibly outside the array, that has a zero index value for each dimension in the array.
Each triplet typically contains a lower bound value, an extent value (or upper bound) and a stride value. A given extent value quantifies a number of elements in a given dimension of the array. A given stride value quantifies a distance in array elements (or machine addressable units) between consecutive array locations in a given dimension. Note that the upper bound for a given dimension equals the lower bound for the given dimension added to the extent for the given dimension plus one. Hence, given a lower bound, the corresponding upper bound can be computed from the extent; likewise the extent can be computed from the upper bound.
Note that a triplet is associated with each dimension of the array. More specifically, dimension one has an associated triplet containing a lower bound 208, an extent or upper bound 210 and a stride 212. Dimension two has an associated triplet containing a lower bound 214, an extent or upper bound 216 and a stride 218. Dimension N has an associated triplet containing a lower bound 220, an extent or upper bound 222 and a stride 224.
One problem with the above-described layout of an array descriptor is that the information needed to perform common array access operations is interspersed with unnecessary information. In modem computer systems, this can lead to a large number of cache misses, which can significantly degrade system performance. This problem is particularly acute for microprocessors with small on-chip caches. This can create significant performance problems for common array access operations if accesses to array descriptors routinely cause cache misses.
One embodiment of the present invention provides a computer readable memory including an array descriptor data structure which contains information on an organization of an array of data values in order to facilitate accesses into the array of data values. This array descriptor data structure includes a starting address of the array in the memory, and a group of extents, including an extent value for each dimension of the array, the extent value for a given dimension quantifying a number of elements in the given dimension. This array descriptor additionally includes a group of strides, including a stride value for each dimension of the array, the stride value of a given dimension quantifying a distance in array elements between consecutive array locations in the given dimension. Also included in the array descriptor data structure is a group of lower bound values, including a lower bound value for each dimension of the array. According to one aspect of the present invention, the group of strides is located in consecutive memory locations, so that an access to an array element through subscripts retrieves strides from consecutive memory locations, thereby exhibiting good cache performance. According to another aspect of the present invention, the group of extents is located in consecutive memory locations, and the group of strides is located in consecutive memory locations, so that a whole array operation, which accesses all locations in the array, first retrieves extents from consecutive memory locations, and then retrieves strides from consecutive memory locations so as to exhibit good cache performance.